package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;
import javafx.util.Pair;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1026 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        int ans = 0;

        public int maxAncestorDiff(TreeNode root) {
            maxAncestorDiffRecur(root);
            return ans;
        }

        public Pair<Integer, Integer> maxAncestorDiffRecur(TreeNode root) {
            if (null == root.left && null == root.right) return new Pair<>(root.val, root.val);
            int curMax = root.val, curMin = root.val;// max and min
            if (null != root.left) {
                Pair<Integer, Integer> leftPair = maxAncestorDiffRecur(root.left);
                ans = Math.max(Math.max(Math.abs(root.val - leftPair.getKey()), Math.abs(root.val - leftPair.getValue())), ans);
                curMax = Math.max(curMax, leftPair.getKey());
                curMin = Math.min(curMin, leftPair.getValue());
            }
            if (null != root.right) {
                Pair<Integer, Integer> rightPair = maxAncestorDiffRecur(root.right);
                ans = Math.max(Math.max(Math.abs(root.val - rightPair.getKey()), Math.abs(root.val - rightPair.getValue())), ans);
                curMax = Math.max(curMax, rightPair.getKey());
                curMin = Math.min(curMin, rightPair.getValue());
            }
            return new Pair<>(curMax, curMin);// max and min
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.maxAncestorDiff(TreeNode.createTree("[8,3,10,1,6,null,14,null,null,4,7,13]")));
        System.out.println(solution.maxAncestorDiff(TreeNode.createTree("[1,null,2,null,0,3]")));
    }

    public static void main(String[] args) throws Exception {
        LC1026 an = new LC1026();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
